home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8990 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB
  1. Path: sdcc12.ucsd.edu!golgi!jstrout
  2. From: Joseph Strout <jstrout@ucsd.edu>
  3. Newsgroups: comp.lang.c++
  4. Subject: fast sorted-list implementation for event-based sim?
  5. Date: Tue, 27 Feb 1996 11:15:17 -0800
  6. Organization: University of California, San Diego
  7. Message-ID: <Pine.SGI.3.91.960227110848.17017C-100000@golgi>
  8. NNTP-Posting-Host: golgi.ucsd.edu
  9. Mime-Version: 1.0
  10. Content-Type: TEXT/PLAIN; charset=US-ASCII
  11. X-Sender: jstrout@golgi
  12.  
  13. I'm considering writing an event-based simulation package.  The needs are 
  14. simple: events go into a collection with an event-time; they may be put 
  15. in in any order (though in general, they will be entered in rough order).
  16. They need to be taken out in order.  Both operations need to be very fast.
  17.  
  18. I've just examined one implementation of such a thing, that builds a big 
  19. (fixed-size) array of events.  To insert an event, it crawls through the 
  20. array to the first unused slot and sticks it there.  To find the next 
  21. event, it goes through all events sequentially, and finds the one with 
  22. the earliest event time.
  23.  
  24. Surely this could be done better?  With a dynamically-allocated linked 
  25. list, for example, we could insert freely at the end of the list, and do 
  26. the Find as above.  Or will all that new'ing and delete'ing slow me down?
  27.  
  28. Perhaps it would be better to maintain the list in sorted order in the 
  29. first place (i.e., as each event is inserted).  This could be done with a 
  30. b-tree structure, I suppose.  (Are there any publicly available 
  31. implementations of such a data structure?)
  32.  
  33. Any advice would be greatly appreciated.  This will be used for 
  34. educational/research freeware, not for commercial purposes.
  35.  
  36. ,------------------------------------------------------------------.
  37. |    Joseph J. Strout           Department of Neuroscience, UCSD   |
  38. |    jstrout@ucsd.edu           http://www-acs.ucsd.edu/~jstrout/  |
  39. `------------------------------------------------------------------'
  40.  
  41.